package com.algrithom.tree.avltree;

/**
 * AVL树
 *
 * @param <T> 泛型
 * @author think
 * @version 1.0.0
 */
public class AvlTree<T extends Comparable> {
    
    private AvlNode<T> root;
    
    AvlTree(){
        this.root = null;
    }
    
    public static void main(String[] args){
        AvlTree<Integer> avlT = createAvlTree();
        System.out.println("Is avl tree:" + avlT.isAVL());
        System.out.println("Mid sort display cur tree===>>>");
        avlT.infPrintTree();
        avlT.remove(60);
        avlT.insert(35);
    }
    
    /**
     * 50 / \ 30 60 / \ 20 40
     *
     * @return AvlTree
     */
    private static AvlTree<Integer> createAvlTree(){
        AvlTree<Integer> avlT = new AvlTree<>();
        avlT.insert(50);
        avlT.insert(60);
        avlT.insert(30);
        avlT.insert(40);
        avlT.insert(20);
        return avlT;
    }
    
    private int height(AvlNode<T> t){
        return t == null ? -1 : t.getHeight();
    }
    
    /**
     * 插入操作
     *
     * @param x 节点
     */
    public void insert(T x){
        this.root = insert(x,root);
    }
    
    /**
     * 删除操作
     *
     * @param x 节点
     */
    public void remove(T x){
        this.root = remove(x,root);
    }
    
    /**
     * 中序打印操作
     */
    public void infPrintTree(){
        infPrintTree(root);
        System.out.println();
    }
    
    /**
     * 判断是否是AVL树
     *
     * @return 状态
     */
    public boolean isAVL(){
        return Math.abs(maxDeep(root.getRight()) - maxDeep(root.getLeft())) < 2;
    }
    
    public AvlNode<T> findMax(AvlNode<T> t){
        if (t == null) {
            throw new RuntimeException("this AvlNode is Empty");
        }
        if (t.getRight() == null) {
            return t;
        }
        return findMax(t.getRight());
    }
    
    public AvlNode<T> insert(T x,AvlNode<T> t){
        if (t == null) { // 传入节点为空，则将该节点作为根节点返回
            return new AvlNode<>(x,null,null);
        }
        int compareResult = x.compareTo(t.getElement());
        if (compareResult < 0) {
            t.setLeft(insert(x,t.getLeft()));
        } else if (compareResult > 0) {
            t.setRight(insert(x,t.getRight()));
        }
        return balance(t);
    }
    
    /**
     * 重新进行平衡
     *
     * @param t 节点
     * @return AVL
     */
    public AvlNode<T> balance(AvlNode<T> t){
        if (t == null) {
            return t;
        }
        // 左插入
        if (height(t.getLeft()) - height(t.getRight()) > 1) {
            // 左左插入  情形1
            if (height(t.getLeft().getLeft()) >= height(t.getLeft().getRight()))
            // 右旋
            {
                t = singleRightRotate(t);
            } else {
                // 左右插入           情形2
                t = doubleLeftRightRotate(t);
            }
        }
        // 右插入
        if (height(t.getRight()) - height(t.getLeft()) > 1) {
            // 右右插入    情形3
            if (height(t.getRight().getRight()) >= height(t.getRight().getLeft())) {
                t = singleLeftRotate(t);
            } else {
                // 右左插入       情形4
                t = doubleRightLeftRotate(t);
            }
        }
        t.setHeight(height(t.getRight()) > height(t.getLeft()) ? height(t.getRight()) + 1 : height(t.getLeft()) + 1);
        return t;
    }
    
    /**
     * 右单旋
     *
     * @param t 节点
     * @return AVL
     */
    private AvlNode<T> singleRightRotate(AvlNode<T> t){
        System.out.println("Dong right rotaion==============>>>");
        AvlNode<T> r = t.getLeft();
        t.setLeft(r.getRight());
        r.setRight(t);
        t.setHeight(height(t.getLeft()) > height(t.getRight()) ? height(t.getLeft()) + 1 : height(t.getRight()) + 1);
        r.setHeight(height(t.getRight()) > height(r) ? height(t.getRight()) + 1 : height(r) + 1);
        return r;
    }
    
    /**
     * 左单旋
     *
     * @param t 节点
     * @return AVL
     */
    private AvlNode<T> singleLeftRotate(AvlNode<T> t){
        System.out.println("Doing left rotaion==============>>>");
        AvlNode<T> r = t.getRight();
        t.setRight(r.getLeft());
        r.setLeft(t);
        t.setHeight(height(t.getLeft()) > height(t.getRight()) ? height(t.getLeft()) + 1 : height(t.getRight()) + 1);
        r.setHeight(height(t.getLeft()) > height(r) ? height(t.getLeft()) + 1 : height(r) + 1);
        return r;
    }
    
    /**
     * 右左双旋
     *
     * @param t 节点
     * @return AVL
     */
    private AvlNode<T> doubleRightLeftRotate(AvlNode<T> t){
        System.out.println("Doing right left double rotation ==============>>>");
        t.setRight(singleRightRotate(t.getRight()));
        return singleLeftRotate(t);
    }
    
    /**
     * 左右双旋
     *
     * @param t 节点
     * @return AVL
     */
    private AvlNode<T> doubleLeftRightRotate(AvlNode<T> t){
        System.out.println("进行左右双旋==============>>>");
        t.setLeft(singleLeftRotate(t.getLeft()));
        return singleRightRotate(t);
    }
    
    public AvlNode<T> remove(T x,AvlNode<T> t){
        // 传入节点为空
        if (t == null) {
            return t;
        }
        int compareResult = x.compareTo(t.getElement());
        if (compareResult < 0) {
            t.setLeft(remove(x,t.getLeft()));
        } else if (compareResult > 0) {
            t.setRight(remove(x,t.getRight()));
        } else if (t.getLeft() != null && t.getRight() != null) {
            // 有两个儿子
            t.setElement(findMax(t.getLeft()).getElement());
            remove(t.getElement(),t.getLeft());
        } else {
            // 单儿子情形
            t = t.getLeft() == null ? t.getRight() : t.getLeft();
        }
        if (t != null) {
            t.setHeight(height(t.getRight()) > height(t.getLeft()) ? height(t.getRight()) + 1 : height(t.getLeft()) + 1);
        }
        return balance(t);
    }
    
    public int maxDeep(AvlNode<T> t){
        // 记录左右树的深度
        int dl, dr;
        if (t == null) {
            return 0;
        } else {
            dl = maxDeep(t.getLeft());
            dr = maxDeep(t.getRight());
        }
        return dl > dr ? dl + 1 : dr + 1;
    }
    
    public void infPrintTree(AvlNode<T> t){
        if (t == null) {
            return;
        }
        infPrintTree(t.getLeft());
        System.out.print(t.getElement() + " ");
        infPrintTree(t.getRight());
    }
}
